package 牛客;

import java.util.Scanner;

public class KY11二叉树的遍历 {
    private static int index = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        //有多个输入
        while(scan.hasNextLine()){
            //每一行的输入用str接受
            String str = scan.nextLine();
            //采用先序遍历的方法将字符串还原成树
            TreeNode root =preOrderBuild(str);
            //按照中序的方式，打印树的节点
            inOrder(root);
            System.out.println();
            //循环结束，将index置为0；
            index = 0;
        }
    }

    /**
     * 给你一个字符串，就能将str按照先序遍历的方式，创建一个树
     * @param str
     * @return
     */
    public static TreeNode preOrderBuild(String str){
        //按照index取出元素
        char cur = str.charAt(index);
        //如果为空，则返回null
        if(cur == '#'){
            return null;
        }
        //否则将当前字符串创建一个节点，作为根节点
        TreeNode root = new TreeNode(cur);
        //开始遍历下一个字符串
        index++;
        //当前根节点的左子树，交给这个方法
        root.left = preOrderBuild(str);
        //二叉树的右子树交给这个方法。
        index++;
        root.right = preOrderBuild(str);
        return root;
    }

    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}
